package com.zhugang.week09;

import java.util.*;

/**
 * @program algorithms
 * @description: openLock
 * @author: chanzhugang
 * @create: 2022/08/22 17:50
 */
public class OpenLock {

    /**
     * 752 打开转盘锁
     *
     * @param deadends
     * @param target
     * @return
     */
    public int openLock(String[] deadends, String target) {
        // 初始值 "0000"，不能和deadends相同，求最小旋转次数
        // BFS:队列、最小深度
        Set<String> deadSet = new HashSet<>();
        for (String d : deadends) {
            deadSet.add(d);
        }
        if (deadSet.contains("0000")) {
            return -1;
        }
        Queue<String> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        queue.offer("0000");
        visited.add("0000");
        int depth = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            int k = 0;
            while (k < size) {
                String node = queue.poll();
                k++;
                if (node.equals(target)) {
                    return depth;
                }
                List<String> newNodes = genNewNode(node);
                for (String newNode : newNodes) {
                    if (visited.contains(newNode) || deadSet.contains(newNode)) {
                        continue;
                    }
                    queue.add(newNode);
                    visited.add(newNode);
                }
            }
            depth++;
        }
        return -1;
    }

    /**
     * 生成相应的8个状态
     *
     * @param node
     * @return
     */
    private List<String> genNewNode(String node) {
        // 这段代码没看明白
        List<String> newNodes = new ArrayList<>();
        int[] changes = {-1, 1};
        for (int i = 0; i < 4; i++) {
            for (int k = 0; k < 2; k++) {
                char[] newNode = new char[4];
                for (int j = 0; j < i; j++) {
                    newNode[j] = node.charAt(j);
                }

                for (int j = i + 1; j < 4; j++) {
                    newNode[j] = node.charAt(j);
                }
                String newC = (((node.charAt(i) - '0') + changes[k] + 10) % 10) + "";
                newNode[i] = newC.charAt(0);
                newNodes.add(new String(newNode));
            }
        }
        return newNodes;
    }
}